1. Field of the Invention
The invention relates generally to error processing in a digital data channel and more specifically relates to improved methods and structures for real time computation of an erasure polynomial to detect and correct data errors from erasure conditions in a digital data channel using Reed-Solomon encoding/decoding.
2. Discussion of Related Art
In digital communication systems it is generally known to transmit or store digital data encoded in forms that improve reliability in reading stored data or receiving transmitted data. Noise on the digital communication channel or other symbol interference generated within the channel or induced in the channel by external signals may cause un-encoded information to be frequently erroneously transmitted or read. Transforming the digital data into encoded sequences based on mathematical spreading of the encoded symbols and generating corresponding error correction and detection codes (“ECC”), such a digital channel may be used in a manner far more immune to noise and interference.
As used herein, “communication” channel includes any receiving components of a digitally encoded channel. For example, a receiver in a digital communication system or a read head in a data storage system are both examples of communication channels that may encounter problems discussed herein and may beneficially apply the features and aspects hereof. Thus “communication channel” and “read channel” may be understood as synonymous in the context of this application.
Exemplary of such digital channels are digital communication channels such as computer or telecommunications network communication media as well as data storage systems wherein data is transmitted to the storage device for storage on a recordable medium as encoded code words and read back from the recordable medium. In communication digital channels, noise and interference may be caused by the analog modulation of the encoded signals and associated analog noise in the ambient environment in which the transmission is performed. In storage applications, the digital channel modulates encoded digital information and associated error correction information onto the associated recordable medium as magnetic flux changes and/or optical property changes on the recordable media. Reading the previously recorded information back, the digital read channel must cope with inter-symbol interference and other aspects of the analog recording of the encoded digital information associated with the magnetic and/or optical storage medium.
It is generally known in the art to utilize Reed-Solomon encoding techniques for high-speed digital communication channels and high-density digital data storage applications. In general, Reed-Solomon encoding techniques encode and embed error correction information along with each encoded unit of transmitted or stored information. Thus, Reed-Solomon encoding as applied in digital communication channels (e.g., telecommunications and/or data storage applications) provides a compact encoding of information including highly effective error correction. Sequences of encoded code words are expected and/or precluded in accordance with the encoding techniques of Reed-Solomon. Thus, as each code word is decoded errors may be detected from the error correction information associated with each code word based on the likelihood of particular code words being encountered in particular sequences.
In addition to correction of erroneous digital data received or retrieved by using Reed-Solomon encoding, other modifications to known Reed-Solomon techniques have been employed to further enhance detecting and correcting erasures of previously stored data. In general, modified Reed-Solomon techniques may also detect and correct erasures of encoded data as distinct from merely erroneous transmission or retrieval of previously encoded information.
As well known to those of ordinary skill in the art, modified Reed-Solomon techniques used to correct both errors and erasures are based upon a discrete time based polynomial expression derived from application of Galois Fields. As used for erasure detection and correction, the Galois Field generator for typical 10-bit code words may be expressed as a discrete time polynomial as follows:m(x)=x10+x3+1
Those of ordinary skill in the art will recognize many other discrete time polynomials that may be utilized for generation of Galois Field values. Thus the above polynomial is intended merely as exemplary of one such discrete time polynomial useful for Galois Field value generation.
A typical Galois Field generator circuit may be implemented as a shift register structure coupled with a summing component as generally known in the field. Exemplary of a known shift register structure in accordance with the above discrete time equation, the Galois Field generator GF(210) may be implemented as a left shift register and summing junction well known to those of ordinary skill in the art. Such a typical Galois Field generator computes the Galois Field (“GF”) element values on each clock cycle in ascending order since each subsequent GF element depends on the previous element. However, as applied to erasure correction as distinct from error correction using Reed-Solomon encoding, the Galois Field elements are utilized in reverse order—e.g., in descending order relative to the ascending order of the received/retrieved code words.
As presently practiced it is impractical to compute each Galois Field element for erasure detection and correction in real time as it is required in the Reed-Solomon decoding process since utilization of the elements in descending order requires re-computation of each earlier element. Such duplicative re-computation of Galois Field elements renders the computational process too slow for real time generation of the Galois Field elements in high speed communication application or high density storage applications. Thus, as presently practiced, the Galois Field elements are generated in ascending order and saved in a lookup table comprised of high speed memory (e.g., a register file or high speed memory circuits) to assure rapid access to the pre-computed GF element values.
It is a problem in such applications that the lookup table used to store pre-computed Galois Field elements may be large. Since the utilized memory structures must be high speed (e.g., a register array) the lookup table circuits may consume substantial circuitry and associated power within the application circuit design for the digital communication channel. For example, a typical GF generator such as GF(210) may require storage of up to 1023 10-bit GF element values. As recording density or transmission speeds increase in the digital communication channel, even larger lookup table structures may be required. Such substantial storage requirements for high speed memory components such as register files represent significant complexity and cost in design of the digital communication channel circuits.
It is evident from the above discussion that a need exists for an improved communication channel design useful in Reed-Solomon erasure detection and correction applications to permit real time error and erasure detection and correction while minimizing circuit complexity and cost area.